package com.xixi.basicAlgroithms.binarySearch;

/**
 * /**
 * A peak element is an element that is strictly greater than its neighbors.
 * <p>
 * Given a 0-indexed integer array nums, find a peak element, and return its
 * index. If the array contains multiple peaks, return the index to any of the peaks.
 * <p>
 * You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is
 * always considered to be strictly greater than a neighbor that is outside the array.
 * <p>
 * <p>
 * You must write an algorithm that runs in O(log n) time.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input: nums = [1,2,3,1]
 * Output: 2
 * Explanation: 3 is a peak element and your function should return the index
 * number 2.
 * <p>
 * Example 2:
 * <p>
 * <p>
 * Input: nums = [1,2,1,3,5,6,4]
 * Output: 5
 * Explanation: Your function can return either index number 1 where the peak
 * element is 2, or index number 5 where the peak element is 6.
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= nums.length <= 1000
 * -2³¹ <= nums[i] <= 2³¹ - 1
 * nums[i] != nums[i + 1] for all valid i.
 * <p>
 * <p>
 * Related Topics 数组 二分查找 👍 920 👎 0
 */


public class ID00162FindPeakElement {
    public static void main(String[] args) {
        Solution solution = new ID00162FindPeakElement().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findPeakElement(int[] nums) {
            int len = nums.length;
            if (len == 1) return 0;

            if (len == 2) return nums[0] > nums[1] ? 0 : 1;

            if (nums[0] > nums[1]) return 0;
            if (nums[len - 1] > nums[len - 2]) return len - 1;

            int left = 1;
            int right = len - 1;

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                    return mid;
                } else if (nums[mid] < nums[mid + 1]) {
                    left = mid + 1;
                } else if (nums[mid] > nums[mid + 1]) {
                    right = mid;
                }
            }

            return left;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}